package com.xigua._排序;

import com.sun.org.apache.regexp.internal.RE;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/4/2415:49
 */
public class _16_最接近的三数之和 {

    public static void main(String[] args) {
        System.out.println(threeSumClosest(new int[]{-3, -2, -5, 3, -4}, -1));
    }

    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = 3000;
        int length = nums.length;
        for (int i = 0; i < length-1; i++) {
            int j = i+1,k = length-1;
            while (j<k){
                int sum = nums[i]+nums[k]+nums[j];
                if (sum==target) return sum;
                if (Math.abs(sum-target)<Math.abs(ans-target)){
                    ans = sum;
                }
                if (sum >target){
                    while (j<k && nums[k] == nums[--k]);
                }else {
                    while (j<k && nums[j] == nums[++j]);
                }

            }
        }
        return ans;
    }
}
